package com.gjx.leetcode;
//81. 搜索旋转排序数组 II
//假设按照升序排序的数组在预先未知的某个点上进行了旋转。
//
//( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
//
//编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
//
//示例 1:
//
//输入: nums = [2,5,6,0,0,1,2], target = 0
//输出: true
//示例 2:
//
//输入: nums = [2,5,6,0,0,1,2], target = 3
//输出: false
//进阶:
//
//这是 搜索旋转排序数组 的延伸题目，本题中的 nums  可能包含重复元素。
//这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？


public class Solution081 {
	public boolean search(int[] nums, int target) {
        
		if (nums == null || nums.length == 0) {
			return false;
		}
		
		int left = 0;
		int right = nums.length-1;
		
		while (left <= right) {
			
			int mid = left + (right - left) / 2;
			
			if (nums[mid] == target) {
				return true;
			} 

			int midLeft = mid;
			while (midLeft >= left && nums[midLeft] == nums[mid]) {
				midLeft--;
			}
			midLeft++;
			int midRight = mid;
			while(midRight <= right && nums[midRight] == nums[mid]) {
				midRight++;
			}
			midRight--;
			
			if (midLeft == left) {
				left = midRight+1;
			} else if (midRight == right) {
				right = midLeft-1;
			} else {
				
				
				if (nums[left] < nums[midLeft]) {
					
					if (nums[left]<=target && target<nums[midLeft]) {
						right = midLeft-1;
					} else {
						left = midRight+1;
					}
					
				} else {
					
					if (nums[midRight] < target && target<=nums[right]) {
						left = midRight + 1;
					} else {
						right = midLeft - 1;
					}
					
				}
				
				
			}
			
		}
		
		return false;
		
    }
	
	
	public static void main(String[] args) {
		new Solution081().search(new int[]{2,5,6,0,0,1,2}, 3);
	}
}
